home *** CD-ROM | disk | FTP | other *** search
- Subject: v17i085: ACM-style programmning contest programs, Part02/03
- Newsgroups: comp.sources.unix
- Approved: rsalz@uunet.UU.NET
-
- Submitted-by: jim nelson <nelson@uncecs.edu>
- Posting-number: Volume 17, Issue 85
- Archive-name: contest-prog/part02
-
- #! /bin/sh
- # This is a shell archive. Remove anything before this line, then unpack
- # it by saving it into a file and typing "sh file". To overwrite existing
- # files, type "sh file -c". You can also feed this as standard input via
- # unshar, or by typing "sh <file", e.g.. If this archive is complete, you
- # will see the following message at the end:
- # "End of archive 2 (of 3)."
- # Contents: Makefile chexec8.c compare.c passwd prob1.c prob13.c
- # prob13.txt prob14.c prob14.txt prob15.txt prob16.c prob16.txt
- # prob17.c prob17.txt prob2.txt prob4.txt prob5.txt prob6.txt sb.c
- # start
- PATH=/bin:/usr/bin:/usr/ucb ; export PATH
- if test -f 'Makefile' -a "${1}" != "-c" ; then
- echo shar: Will not clobber existing file \"'Makefile'\"
- else
- echo shar: Extracting \"'Makefile'\" \(2655 characters\)
- sed "s/^X//" >'Makefile' <<'END_OF_FILE'
- XCC=cc
- XCFLAGS= -s -O
- X.IGNORE:
- X#a public directory such as /usr/local
- XLOCAL=/usr/contest
- X#the judges directory
- XJUDGES=/usr2/judges
- X#the judges group
- XGROUP=453
- X#where the scoreboard is
- X#this really should be a dependecy on a .h file for just score.c
- X#but it's really easier just now to :
- XSCOREBOARD=\"$(JUDGES)/scoreboard\"
- X
- X#parallel make flag for sequent only:
- X#P=&
- X#(only, I guess, sequent people appreciate the & flag)
- X#maybe others have a similar thingie ... but I cannot know.
- X
- X#below here shouldn't need modifying (?)
- X
- XTBEG=prob1.txt prob2.txt prob3.txt prob4.txt prob5.txt prob6.txt
- X#TINT=prob7.txt prob8.txt prob9.txt prob10.txt prob11.txt prob12.txt
- XTADV=prob13.txt prob14.txt prob15.txt prob16.txt prob17.txt prob18.txt
- XTSRC= $(TBEG) $(TINT) $(TADV)
- X
- XCBEG=prob1.c prob2.c prob3.c prob4.c prob5.c prob6.c
- X#CINT=prob7.c prob8.c prob9.c prob10.c prob11.c prob12.c
- XCADV=prob13.c prob14.c prob15.c prob16.c prob17.c prob18.c
- XCSRC= $(CBEG) $(CINT) $(CADV)
- X
- XABEG=prob1.ans prob2.ans prob3.ans prob4.ans prob5.ans prob6.ans
- X#AINT=prob7.ans prob8.ans prob9.ans prob10.ans prob11.ans prob12.ans
- XAADV=prob13.ans prob14.ans prob15.ans prob16.ans prob17.ans prob18.ans
- XANS= $(ABEG) $(AINT) $(AADV)
- X
- XIBEG=prob1.in prob2.in prob3.in prob4.in prob5.in prob6.in
- X#IINT=prob7.in prob8.in prob9.in prob10.in prob11.in prob12.in
- XIADV=prob13.in prob14.in prob15.in prob16.in prob17.in prob18.in
- XIN=$(IBEG) $(IINT) $(IADV)
- X
- XALLC=$(CSRC) compare.c score.c seconds.c chexec8.c syserr.c digits.c \
- Xshorten.c sb.c
- XOTHER=n passwd start f sf README Makefile gr testem judge visc \
- Xshutofflogins scoreascorrect scoreasincorre scoreboard
- X
- Xall: $(P) chexec8 seconds compare score judge gr shorten digits \
- Xtestem
- X chmod +x gr judge testem
- X testem
- X
- Xinstall:
- X mkdir keep
- X mkdir subdir
- X mkdir $(LOCAL)
- X chmod 777 $(LOCAL)
- X cp seconds $(LOCAL)
- X chmod +rx $(LOCAL)/seconds
- X sed s/GROUP/$(GROUP)/ judge > $(LOCAL)/judge
- X chmod +rx $(LOCAL)/judge
- X cp score $(LOCAL)
- X chmod 755 $(LOCAL)/score
- X chmod u+s $(LOCAL)/score
- X
- Xshar: $(TSRC) $(ALLC) $(ANS) $(IN) $(OTHER)
- X makekit -m -s30k rules contestrules \
- X $(TSRC) $(ALLC) $(ANS) $(IN) $(OTHER)
- X
- Xpasswd: shutofflogins
- X shutofflogins
- X
- Xchexec8: $(P) chexec8.o syserr.o
- X cc -o chexec8 chexec8.o syserr.o
- X
- Xseconds: seconds.o
- X cc -o seconds seconds.o
- X
- Xshorten: shorten.o
- X cc -o shorten shorten.o
- X
- Xcompare: compare.o
- X cc -o compare compare.o
- X
- Xdigits: digits.o
- X cc -o digits digits.o
- X
- Xscore: score.o Makefile
- X cc -o score -s score.o
- X
- Xscore.o: score.c Makefile
- X cc -c -DSCOREBOARD=$(SCOREBOARD) score.c
- X
- Xscoretime:
- X cp /dev/null scoretime
- X
- Xsend:
- X uuto Part* 3b2b\!judges
- X
- Xclean:
- X rm *.e *.o Part* chexec8 seconds compare score digits shorten
- X
- END_OF_FILE
- if test 2655 -ne `wc -c <'Makefile'`; then
- echo shar: \"'Makefile'\" unpacked with wrong size!
- fi
- # end of 'Makefile'
- fi
- if test -f 'chexec8.c' -a "${1}" != "-c" ; then
- echo shar: Will not clobber existing file \"'chexec8.c'\"
- else
- echo shar: Extracting \"'chexec8.c'\" \(882 characters\)
- sed "s/^X//" >'chexec8.c' <<'END_OF_FILE'
- X#include <stdio.h>
- X/*#include <fcntl.h>*/
- X#include <signal.h>
- X/*#include <sys/wait.h>*/
- Xint k;
- Xmain(argc,argv)
- Xchar **argv;
- X{
- X int childstatus(),oops();
- X setuid(getuid());
- X k=fork();
- X if(k){
- X signal(SIGALRM,oops);
- X#ifndef SIGCHLD
- X#define SIGCHLD SIGCLD
- X#endif
- X/*CHLD=20 for dynix, CLD=18 for SysV2*/
- X/* anyway what we want is to catch "death of child" signal*/
- X signal(SIGCHLD,childstatus);
- X alarm(10);
- X wait(0);}
- X else
- X execl(argv[1],"dumbo",0);
- X}
- Xchildstatus(sig,code,x)
- X{
- X int i,j,m;
- X
- X fprintf(stderr,"sig=%d,code=%d, k=%d\n",sig,code,k);
- X
- X for(i=0;i<200;i++){
- X j=k+i;
- X j= j % 32768;
- X if(j>1){
- X m=kill(j,9);
- X if(m>=0)fprintf(stderr,"killed %d ",j);
- X }
- X }
- X
- X exit(0);
- X}
- Xoops(sig,code,x)
- X{
- X fprintf(stderr,"sig=%d,code=%d\n",sig,code);
- X fprintf(stderr,"there may be a daemon attack underway\n");
- X fprintf(stderr,"kill %d\n",k);
- X childstatus(sig,code,x);
- X exit(1);
- X}
- X
- END_OF_FILE
- if test 882 -ne `wc -c <'chexec8.c'`; then
- echo shar: \"'chexec8.c'\" unpacked with wrong size!
- fi
- # end of 'chexec8.c'
- fi
- if test -f 'compare.c' -a "${1}" != "-c" ; then
- echo shar: Will not clobber existing file \"'compare.c'\"
- else
- echo shar: Extracting \"'compare.c'\" \(1085 characters\)
- sed "s/^X//" >'compare.c' <<'END_OF_FILE'
- X#include <stdio.h>
- X#define tab '\t'
- X#define null '\0'
- X#define newline '\n'
- Xmain(argc,argv)
- Xchar **argv;
- X{
- X FILE *fpa, *fpb;
- X char linea[200], lineb[200];
- X char tempa[200], tempb[200];
- X
- X char *p, *q;
- X int eofa=0,eofb=0;
- X int compare;
- X if(argc!=3)exit(1);
- X
- X fpa=fopen(argv[1],"r");
- X if(fpa==(FILE *)0)exit(2);
- X
- X fpb=fopen(argv[2],"r");
- X if(fpb==(FILE *)0)exit(3);
- X eofa=eofb=0;
- X compare=0;
- Xread:
- X if(!eofa)if(fgets(linea,199,fpa)!=linea)eofa=1;
- X if(!eofb)if(fgets(lineb,199,fpb)!=lineb)eofb=1;
- X if(eofa && eofb)exit(compare);
- X
- X if(eofa&& !eofb)exit(4);
- X if(eofb&& !eofa)exit(5);
- X if(eofa || eofb)exit(6);
- X
- Xfor(p=linea;*p;p++){if(*p==tab) *p=' ';if(*p==newline) *p=0;}
- Xfor(p=lineb;*p;p++){if(*p==tab) *p=' ';if(*p==newline) *p=0;}
- X p=linea;
- X q=lineb;
- Xtightloop:
- X while(*p==' ' || *p==tab || *p==newline)p++;
- X while(*q==' ' || *q==tab || *q==newline)q++;
- X if(*p!= *q){
- X printf("them: %s\n",linea);
- X printf(" us: %s\n",lineb);
- X compare=1;
- X puts("------------------------------------");
- X goto read;
- X }
- X else{
- X p++;
- X q++;
- X if(*p==null)if(*q==null)goto read;
- X goto tightloop;
- X }
- X
- X}
- END_OF_FILE
- if test 1085 -ne `wc -c <'compare.c'`; then
- echo shar: \"'compare.c'\" unpacked with wrong size!
- fi
- # end of 'compare.c'
- fi
- if test -f 'passwd' -a "${1}" != "-c" ; then
- echo shar: Will not clobber existing file \"'passwd'\"
- else
- echo shar: Extracting \"'passwd'\" \(1863 characters\)
- sed "s/^X//" >'passwd' <<'END_OF_FILE'
- Xroot:Jfy5vADKI.PUo:0:0:Admin:/:/bin/csh
- Xdaemon:*:1:10:Admin:/:
- Xusrlimit:HVhogDpnYyySg:2:2:This is a 32 user system, DO NOT REMOVE THIS LINE:/:/dev/null
- Xuucp:LHFftElncpbcU:66:10:uucp owner:/usr/lib/uucp:/bin/csh
- X3b2b::67:10:UNIX-to-UNIX Copy:/usr/spool/uucppublic:/usr/lib/uucp/uucico
- X3b2a::68:10:UNIX-to-UNIX Copy:/usr/spool/uucppublic:/usr/lib/uucp/uucico
- Xlmc::69:10:UNIX-to-UNIX Copy:/usr/spool/uucppublic:/usr/lib/uucp/uucico
- Xsigma::71:10:UNIX-to-UNIX Copy:/usr/spool/uucppublic:/usr/lib/uucp/uucico
- Xcltsqnt::72:10:sequent:/usr/spool/uucppublic:/usr/lib/uucp/uucico
- Xnelson:TQQhhbK575Jtc:100:0:j h nelson,MO-263,3300,3926032/3955570/147.53,:/usr1/nelson:/bin/csh
- Xherbst:hwshDCyvtoI.s:104:100:R.T. Herbst,MO 256,3248,2563304,universe(ucb):/usr1/herbst:
- Xguest::105:100:a guest:/usr1/guest:/usr/uncw/score
- Xscore::105:100:a guest:/usr1/guest:/usr/uncw/score
- Xwhipkey:HinSCYmbORBjk:116:100:k whipkey:/usr1/whipkey:
- Xsmithh:7g3ZmER5p4epA:123:100:H.F. Smith,CH 200-E,3953819,,:/usr1/smithh:
- Xnorris:8F42zTTbXo3Ak:125:100:f r norris,264,3953301,,:/usr1/norris:/bin/csh
- Xjudges:8HrGYoJq3fxdQ:453:453:the judges,,,,:/usr2/judges:/bin/csh
- Xteam1:mrCEcc.F8UocI:478:478:team1:/usr1/team1:/bin/csh
- Xteam2:6DsWELtbNWOLg:479:479:team2:/usr1/team2:/bin/csh
- Xteam3:BRc8uYjDHRO6.:480:480:team3:/usr2/team3:/bin/csh
- Xteam4:Icegxkv..vEcQ:481:481:team4:/usr2/team4:/bin/csh
- Xteam5:BjLwNCM7HePeU:482:482:team5:/usr2/team5:/bin/csh
- Xteam6:Oo3fEvH61VKeo:483:483:team6:/usr2/team6:
- Xteam7:k0isgx3nuFK1Q:484:484:team7:/usr3/team7:
- Xteam8:h35xJdDATkW5Y:485:485:team8:/usr3/team8:
- Xteam9:foTUAMb51CRDM:486:486:team9:/usr1/team9:
- Xteam10:b/vzhtWaiNAJA:487:487:team10:/usr1/team10:
- Xteam11:6LmSPFh9PpBDw:488:488:team11:/usr3/team11:
- Xteam12:omg0gx1Lw2lr2:489:489:team12:/usr3/team12:/bin/csh
- Xteam13:FlwviGdBAAXFE:490:490:team13:/usr3/team13:/bin/csh
- Xteam14:kYWLsTLpfiLFg:491:491:team14:/usr3/team14:/bin/csh
- END_OF_FILE
- if test 1863 -ne `wc -c <'passwd'`; then
- echo shar: \"'passwd'\" unpacked with wrong size!
- fi
- # end of 'passwd'
- fi
- if test -f 'prob1.c' -a "${1}" != "-c" ; then
- echo shar: Will not clobber existing file \"'prob1.c'\"
- else
- echo shar: Extracting \"'prob1.c'\" \(829 characters\)
- sed "s/^X//" >'prob1.c' <<'END_OF_FILE'
- Xmain()
- X{
- X int *left, *right, *doub;
- X int l,m, i=0,j,k;
- X int nd=0;
- X char *malloc();
- Xleft=(int *)malloc(500*sizeof(int));
- Xright=(int *)malloc(500*sizeof(int));
- Xdoub=(int *)malloc(500*sizeof(int));
- X
- X for(i=0;i<500;i++)doub[i]=0;
- X i=0;
- X while( scanf("%d%d",&j,&k)==2)
- X if(j>=0 && k>=0){left[i]=j; right[i]=k; i++;}
- X else break;
- X i--;
- X for (j=0;j<=i;j++)
- X {
- X k=left[j];
- X for(m=0;m<=i;m++)if(k==right[m]){doub[nd++]=k;break;}
- X }
- X if(nd){
- X/* for(i=0;i<nd;i++)if(doub[i])printf("%d\n",doub[i]);*/
- X
- X if(nd>=2){
- X for(i=0;i<nd-1;i++)
- X for(j=i+1;j<nd;j++)
- X if(doub[i]>doub[j]){k=doub[i];doub[i]=doub[j];doub[j]=k;}
- X else {}
- X }else printf("%d\n",doub[0]);
- X
- X }else{}
- X doub[nd]= -1;
- X/* for(i=0;i<nd;i++)if(doub[i])
- Xprintf("%d\n",doub[i]);
- X*/
- X
- Xk= -1;
- X
- X for(i=0;i<nd;i++)if(doub[i]!=doub[i+1])
- Xprintf("%d\n",doub[i]);
- X
- X return 0;
- X}
- END_OF_FILE
- if test 829 -ne `wc -c <'prob1.c'`; then
- echo shar: \"'prob1.c'\" unpacked with wrong size!
- fi
- # end of 'prob1.c'
- fi
- if test -f 'prob13.c' -a "${1}" != "-c" ; then
- echo shar: Will not clobber existing file \"'prob13.c'\"
- else
- echo shar: Extracting \"'prob13.c'\" \(2166 characters\)
- sed "s/^X//" >'prob13.c' <<'END_OF_FILE'
- Xmain(){
- X int oldop,mask,flag;
- X#define newline '\n'
- X#define null '\0'
- X /*
- XFrom norris Fri Nov 11 11:06:03 1988
- XBinary-binary
- X
- X Mathematicians refer to addition and subtraction as binary
- Xoperations. Since computer scientists like to take things much
- Xfarther than they were intended, you are going to write a
- Xbinary binary calculator.
- X This calculator program will accept infix expressions involving
- Xonly + and - and unsigned binary integers. No parentheses or
- Xother operations will be present. You must compute the value
- Xof the expression and display the result in binary. Negative
- Xresults should be printed with a leading minus sign.
- X Data considerations:
- X Input will consist of an unspecified number of expressions,
- X one per line; end-of-file will indicate the end of data. Each
- X expression will contain no leading or embedded blanks. No
- X expression will contain more than 80 characters. The
- X expression values are to be computed left-to-right. No
- X number or intermediate value will require more than 15 bits
- X of precision. Output should start in column 1 of the
- X output file, one result per line, with no leading zeroes.
- X
- XExample:
- X the input expression: 110+11-1+100
- X results in the output
- X1100
- X
- X the input expression: 1100-11000+111-10
- X results in the output
- X-111
- X*/
- X char line[90];
- X int sum,n;
- X char *p;
- X char *gets();
- X while( gets(line)==line ){
- X p=line;
- X n=0;
- X for(p=line,n=0,sum=0,oldop='+';;p++) {
- X switch(*p){
- X case '-':
- X case '+':
- X if(oldop=='+')sum += n;
- X else sum -=n;
- X n=0;
- X oldop= *p;
- X break;
- X case '0':
- X n= n* 2;
- X break;
- X case '1':
- X n= n*2+1;
- X break;
- X case newline:
- X case 0:
- X if(oldop=='+')sum += n;
- X else sum -=n;
- X goto out;
- X/* n=0; */
- X/* oldop= *p;*/
- X break;
- X default:
- X ;
- X }
- X }
- Xout: /*printf("%d\n",sum);*/
- X ;
- X if(sum==0){
- X putchar('0');
- X putchar(newline);
- X continue;
- X }
- X if(sum<0){
- X putchar('-');
- X sum = - sum;
- X }
- X for(mask=0100000, flag=0; mask; mask >>=1){
- X
- X if(sum & mask ){
- X putchar('1');
- X flag=1;
- X } else if(flag)putchar('0');
- X }
- X putchar(newline);
- X
- X }/*endwhile gets*/
- X}/*end main*/
- END_OF_FILE
- if test 2166 -ne `wc -c <'prob13.c'`; then
- echo shar: \"'prob13.c'\" unpacked with wrong size!
- fi
- # end of 'prob13.c'
- fi
- if test -f 'prob13.txt' -a "${1}" != "-c" ; then
- echo shar: Will not clobber existing file \"'prob13.txt'\"
- else
- echo shar: Extracting \"'prob13.txt'\" \(1400 characters\)
- sed "s/^X//" >'prob13.txt' <<'END_OF_FILE'
- XProblem 13: Binary-binary.
- X
- X Mathematicians refer to addition and subtraction as binary
- Xoperations. Since computer scientists like to take things much
- Xfarther than they were intended, you are going to write a
- Xbinary binary calculator.
- X This calculator program will accept infix expressions involving
- Xonly + and - and unsigned binary integers. No parentheses or
- Xother operations will be present. You must compute the value
- Xof the expression and display the result in binary. Negative
- Xresults should be printed with a leading minus sign.
- X Data considerations:
- X Input will consist of an unspecified number of expressions,
- X one per line; end-of-file will indicate the end of data. Each
- X expression may contain leading or embedded blanks; however, no
- X number will contain embedded blanks.
- X A totally blank line should evoke an output of '0'.
- X No expression will contain more than 80 characters. The
- X expression values are to be computed left-to-right. No
- X number or intermediate value will require more than 15 bits
- X of precision. Output should start in column 1 of the
- X output file, one result per line, with no leading zeroes.
- X
- XExample:
- X the input expression: 110+11- 1 +100
- X results in the output
- X1100
- X
- X the input expression: 1100 - 11000+111-10
- X results in the output
- X-111
- X
- X the input expression: <a blank line>
- X results in the output
- X0
- END_OF_FILE
- if test 1400 -ne `wc -c <'prob13.txt'`; then
- echo shar: \"'prob13.txt'\" unpacked with wrong size!
- fi
- # end of 'prob13.txt'
- fi
- if test -f 'prob14.c' -a "${1}" != "-c" ; then
- echo shar: Will not clobber existing file \"'prob14.c'\"
- else
- echo shar: Extracting \"'prob14.c'\" \(1054 characters\)
- sed "s/^X//" >'prob14.c' <<'END_OF_FILE'
- Xmain(){
- X int a[4];
- X int numfnd = -1;
- X int this, found[10000];
- X int t;
- X int p,q,r,s,i,j,k,l,n;
- X for(i=0;i<10;i++)
- X for(j=0;j<10;j++)if(i==j)continue;
- X else
- X for(k=0;k<10;k++)
- X for(l=0;l<10;l++)if(k==l)continue;
- X else
- X {
- X p=i*10+j;
- X q=k*10+l;
- X
- X r=j*10+i;
- X s=l*10+k;
- X if(p==r || p==s ||q==r||q==s)continue;
- X else
- X if((n=p*q) == r*s){
- X int i,j;
- X /*bingo*/
- X a[0]=p;
- X a[1]=q;
- X a[2]=r;
- X a[3]=s;
- Xxxx:
- X for(i=0;i<4;i++)for(j=i;j<4;j++)if(a[i]>a[j]){
- X t=a[i];
- X a[i]=a[j];
- X a[j]=t;
- X goto xxx;
- X }
- X /*printf("%d %d %d %d %d " ,p,q,r,s,n);*/
- X this=a[0]*1000000+a[1]*10000+a[2]*100+a[3];
- X if(numfnd== -1){
- X found[++numfnd]=this;
- X printf("%d %d\n",a[0],n);
- X continue;
- X }
- X else{
- X t=0;
- X for(i=0;i<=numfnd;i++)if(found[i]==this)t=1;
- X }
- X if(!t)
- X {
- X found[++numfnd]=this;
- X printf("%d %d\n",a[0],n);
- X }
- X else /*putchar('\n')*/ ;
- X }
- X }
- X
- X
- X}
- END_OF_FILE
- if test 1054 -ne `wc -c <'prob14.c'`; then
- echo shar: \"'prob14.c'\" unpacked with wrong size!
- fi
- # end of 'prob14.c'
- fi
- if test -f 'prob14.txt' -a "${1}" != "-c" ; then
- echo shar: Will not clobber existing file \"'prob14.txt'\"
- else
- echo shar: Extracting \"'prob14.txt'\" \(1119 characters\)
- sed "s/^X//" >'prob14.txt' <<'END_OF_FILE'
- XProblem 14: Reverse products.
- X
- X
- XThe product 64 * 69 = 4416, and so also is the product 46 * 96 with the
- Xdigits reversed in both numbers. Write a program that prints all such
- Xpairs of two-digit numbers with this property. For purposes of this
- Xproblem, numbers less than 10 are to be considered two-digit numbers.
- XHowever, exclude the following: numbers having the same two digits
- X(e.g., 77), pairs where one of the original numbers is just the
- Xreverse of the other (e.g., 46 and 64), and any DUPLICATE sets of
- Xnumbers (i.e., the foursome 46, 64, 69, 96 should be found just once).
- XThe output for this problem should consist of lines,
- Xeach with two values: p = the smallest element of a foursome, and
- Xq = the corresponding product value. Thus, the line for this example
- Xcase would contain: 46 4416. Moreover, the lines should be
- Xordered by values of p, and then by values of q in case of
- Xrepetitions of p values.
- X
- XThere is no input file for this problem.
- X
- XSample output:
- X1 20 <this is tricky: comes from 01*20 == 10*02 >
- X1 30
- X ...
- X ...
- X34 2924
- X ...
- X
- XHint: there are fifty output lines in a correct answer.
- END_OF_FILE
- if test 1119 -ne `wc -c <'prob14.txt'`; then
- echo shar: \"'prob14.txt'\" unpacked with wrong size!
- fi
- # end of 'prob14.txt'
- fi
- if test -f 'prob15.txt' -a "${1}" != "-c" ; then
- echo shar: Will not clobber existing file \"'prob15.txt'\"
- else
- echo shar: Extracting \"'prob15.txt'\" \(1064 characters\)
- sed "s/^X//" >'prob15.txt' <<'END_OF_FILE'
- XProblem 15: Circular execution.
- X
- X
- XYou and your friends are suddenly rounded up into a circle. You are told
- Xthat, starting from the head of the circle, THEY will count to M, execute
- Xthat Mth person, close the circle, and repeat this process until just one
- Xperson is left to escape. Given that there are N persons and that the
- Xrule is to execute every Mth person, you need to decide which position
- Xto take in the circle if you are to remain alive.
- X
- XWrite a program that reads and computes, for four pairs of (M,N) values.
- XFor each pair, as your program executes (literally!), have it print out the
- Xidentity of each person as he is eliminated. For example, with M = 7 and
- XN = 11, the output would be: 7 3 11 9 8 10 2 6 1 4 5
- X(showing 5 (the last guy in the list) surviving).
- X
- XThere will be exactly four M,N pairs in the input datafile, two per line.
- XM and N will each be less than or equal to 20.
- XSuch as:
- X7 11
- X9 13
- X13 15
- X7 14
- X
- XNote that there is NO requirement that M be less than N.
- X
- XBe careful that your output consists of exactly four lines.
- END_OF_FILE
- if test 1064 -ne `wc -c <'prob15.txt'`; then
- echo shar: \"'prob15.txt'\" unpacked with wrong size!
- fi
- # end of 'prob15.txt'
- fi
- if test -f 'prob16.c' -a "${1}" != "-c" ; then
- echo shar: Will not clobber existing file \"'prob16.c'\"
- else
- echo shar: Extracting \"'prob16.c'\" \(1273 characters\)
- sed "s/^X//" >'prob16.c' <<'END_OF_FILE'
- Xmain(){
- X int ii,jj,kk,a,b,M,N,i,j,k;
- X int abin,bbin,nbin[200],bin[200][30];
- X
- X scanf("%d%d",&M,&N);
- X for(i=1;i<=N;i++){
- X bin[i][1]=i;
- X nbin[i]=1;
- X }
- X for(kk=1;kk<=M;kk++){
- X if(scanf("%d%d",&a,&b)!=2)exit(1);
- X ii=jj=0;
- X for(i=1;i<=N;i++){
- X if(nbin[i]<1)continue;
- X for(j=1;j<=nbin[i];j++)
- X if(bin[i][j]==a){
- X ii=i;
- X jj=j;
- X }
- X }
- X if(ii==0||jj==0){
- X printf("oops a=%d b=%d ii=%d jj=%d i=%d j=%d nbin[ii]=%d\n"
- X ,a,b,ii,jj,i,j,nbin[ii]);
- X exit(2);
- X }
- X /*bin[ii][jj]=0;*/
- X abin=ii;
- X ii=jj=0;
- X for(i=1;i<=N;i++){
- X if(nbin[i]<1)continue;
- X for(j=1;j<=nbin[i];j++)
- X if(bin[i][j]==b){
- X ii=i;
- X jj=j;
- X break;
- X }
- X }
- X if(ii==0||jj==0){
- X printf("oops ii=%d jj=%d i=%d j=%d nbin[ii]=%d\n"
- X ,ii,jj,i,j,nbin[ii]);
- X exit(3);
- X }
- X bbin=ii;
- X for(j=1;j<=nbin[abin];j++)bin[bbin][++nbin[bbin]]=bin[abin][j];
- X nbin[abin]=0;
- X }
- X for(i=1;i<=N;i++)
- X {
- X k=nbin[i];
- X if(k<1)continue;
- X if(k>=2){
- X int l,m;
- X for(l=1;l<k;l++)for(m=l+1;m<=k;m++)if(bin[i][l]>bin[i][m]){
- X int t;
- X t=bin[i][l];
- X bin[i][l]=bin[i][m];
- X bin[i][m]=t;
- X }
- X }
- X }
- X for(i=1;i<=N;i++)
- X for(kk=1;kk<=N;kk++)
- X if(nbin[kk]<1)continue; else{
- X if(bin[kk][1]==i){
- X for(j=1;j<=nbin[kk];j++) printf(" %d ",bin[kk][j]);
- X puts("");
- X
- X }
- X }
- X
- X}
- END_OF_FILE
- if test 1273 -ne `wc -c <'prob16.c'`; then
- echo shar: \"'prob16.c'\" unpacked with wrong size!
- fi
- # end of 'prob16.c'
- fi
- if test -f 'prob16.txt' -a "${1}" != "-c" ; then
- echo shar: Will not clobber existing file \"'prob16.txt'\"
- else
- echo shar: Extracting \"'prob16.txt'\" \(1059 characters\)
- sed "s/^X//" >'prob16.txt' <<'END_OF_FILE'
- XProblem 16: Equivalence classes.
- X
- X
- XSuppose that we have a set of N objects {a[i]}. We are also given M statements
- Xof the form a[i] == a[j] . Let us assume that the objects have been mapped into
- Xthe integers 1 .. N by some manner. For example, with N = 19 and M = 16, we
- Xmight have the following objects and relationships:
- X 18 = 12 16 = 14 8 = 18 16 = 6
- X 6 = 10 9 = 1 17 = 4 16 = 17
- X 8 = 2 3 = 13 9 = 11 3 = 8
- X 11 = 5 7 = 19 3 = 9 19 = 15
- XWrite a program that reads M and N, followed by the M pairings i = j,
- Xwith i and j both in the range 1 .. N. Your program should compute which
- Xobjects fall into which classes of equivalent objects, and should then
- Xprint out these classes, as follows: objects sorted within each class,
- Xand classes printed in order of their first members. Thus, for the example
- Xabove, the output would be:
- X 1 2 3 5 8 9 11 12 13 18
- X 4 6 10 14 16 17
- X 7 15 19
- X
- END_OF_FILE
- if test 1059 -ne `wc -c <'prob16.txt'`; then
- echo shar: \"'prob16.txt'\" unpacked with wrong size!
- fi
- # end of 'prob16.txt'
- fi
- if test -f 'prob17.c' -a "${1}" != "-c" ; then
- echo shar: Will not clobber existing file \"'prob17.c'\"
- else
- echo shar: Extracting \"'prob17.c'\" \(787 characters\)
- sed "s/^X//" >'prob17.c' <<'END_OF_FILE'
- X#include <stdio.h>
- Xmain(){
- X int z,s,x[4],y[4],tx,ty,xi,yi,abig,area();
- X char *p;
- X int t=0,i,k;
- X while( scanf("%d%d",&x[1],&y[1]) == 2){
- X scanf("%d%d",&x[2],&y[2]);
- X scanf("%d%d",&x[3],&y[3]);
- X t++;
- X for(k=1;k<=7;k++){
- X scanf("%d%d",&tx,&ty);
- X abig=area(x,y);
- X s=(int)0;
- X for(i=1;i<=3;i++){
- X xi=x[i];
- X x[i]=tx;
- X yi=y[i];
- X y[i]=ty;
- X s +=area(x,y);
- X x[i]=xi;
- X y[i]=yi;
- X
- X }
- X z=s-abig;
- X if(z<0)z= -z;
- X if(z==0){
- X/* fprintf(stderr,"yes\n");*/
- X p="inside";}
- X else {
- X/* fprintf(stderr,"no\n");*/
- X p="outside";}
- X printf("%d %d is %s triangle %d\n",(int)(tx),(int)(ty),p,t);
- X/* fprintf(stderr,"\n");*/
- X }
- X }
- X}
- Xint area(x,y)
- Xint x[],y[];
- X{
- X int z;
- X z= (x[1]*y[2]-x[1]*y[3]+x[2]*y[3]-x[2]*y[1]+x[3]*y[1]-x[3]*y[2]);
- X/* z= z ;*/
- X if(z<0)z = -z;
- X/* fprintf(stderr,"area=%d ",z);*/
- X return z;
- X}
- END_OF_FILE
- if test 787 -ne `wc -c <'prob17.c'`; then
- echo shar: \"'prob17.c'\" unpacked with wrong size!
- fi
- # end of 'prob17.c'
- fi
- if test -f 'prob17.txt' -a "${1}" != "-c" ; then
- echo shar: Will not clobber existing file \"'prob17.txt'\"
- else
- echo shar: Extracting \"'prob17.txt'\" \(936 characters\)
- sed "s/^X//" >'prob17.txt' <<'END_OF_FILE'
- XProblem 17: Point inside triangle.
- X
- XWhen is a point (s,t) inside a triangle with vertices (x1, y1),
- X(x2, y2), (x3, y3)?? For this problem, the input will contain 20
- Xlines containing coordinate pairs:
- X three lines with coordinates of three vertices of first triangle
- X seven lines, each with coordinates of a point to be tested therein
- X three lines with coordinates of three vertices of second triangle
- X seven lines, each with coordinates of a point to be tested therein
- X
- XFor example, if the first five lines of input were
- X 3 2
- X 6 10
- X 15 7
- X 5 7
- X 14 6
- Xthe corresponding output would be
- X 5 7 is inside triangle 1
- X 14 6 is outside triangle 1
- X
- XSpacing of the output is not important, but you must have the words
- X"is", "inside" or "outside", and "triangle" in your output, just as
- Xin the example.
- X
- XThe vertices of the triangle, and the test point, are guaranteed to
- Xbe integers.
- X
- END_OF_FILE
- if test 936 -ne `wc -c <'prob17.txt'`; then
- echo shar: \"'prob17.txt'\" unpacked with wrong size!
- fi
- # end of 'prob17.txt'
- fi
- if test -f 'prob2.txt' -a "${1}" != "-c" ; then
- echo shar: Will not clobber existing file \"'prob2.txt'\"
- else
- echo shar: Extracting \"'prob2.txt'\" \(1204 characters\)
- sed "s/^X//" >'prob2.txt' <<'END_OF_FILE'
- XProblem 2: Character count.
- X
- XFor all the lines in a file, count the occurrences of the
- Xvarious characters in that file.
- X
- XThe input file will be a text file of unknown length, but
- Xwith each line guaranteed to be less than 80 characters long.
- X
- XThe input file may contain tabs (ascii octal 011), blanks,
- Xand all the printable characters, as well as newlines.
- X
- XDo not attempt to count newlines; only tabs, blanks, and printable
- Xcharacters.
- X
- XYour output should consist of two integers per line. The leftmost
- Xshould be the ascii character printed in decimal form, the rightmost
- Xshould be the count of the character.
- X
- XBUT: do not output zero-counts. That is: do not print any line
- Xfor which the count is zero.
- X
- XExample:
- Xtime for all
- X good men to
- Xcome to the aid of
- X
- X(note that the word "good" is preceded by a tab-character).
- X
- XShould produce:
- X 9 1 <this is the tab>
- X 32 8 <this is "blank">
- X 97 2 <this is "a">
- X 99 1 <etc., and of course, you don't
- X 100 2 print these comments>
- X 101 4
- X 102 2
- X 103 1
- X 104 1
- X 105 2
- X 108 2
- X 109 3
- X 110 1
- X 111 7
- X 114 1
- X 116 4
- END_OF_FILE
- if test 1204 -ne `wc -c <'prob2.txt'`; then
- echo shar: \"'prob2.txt'\" unpacked with wrong size!
- fi
- # end of 'prob2.txt'
- fi
- if test -f 'prob4.txt' -a "${1}" != "-c" ; then
- echo shar: Will not clobber existing file \"'prob4.txt'\"
- else
- echo shar: Extracting \"'prob4.txt'\" \(864 characters\)
- sed "s/^X//" >'prob4.txt' <<'END_OF_FILE'
- XProblem 4: Print odds and evens side-by-side.
- X
- XThe input file will consist of some positive integers. The number
- Xof integers will be less than thirty. Each integer will be
- Xgreater than or equal to one. The last line of the input file
- Xwill contain a negative number, for use as a sentinel. There will
- Xbe one integer per line, left justified, beginning in column 1.
- X
- XThe output is to consist of lines of the form:
- Xodd number even number
- X
- Xwhere the numbers are those from the input file, in the order in
- Xwhich they occurred.
- X
- XIf there are fewer odd numbers than even numbers, pad with -1 .
- XIf there are fewer even numbers than odd numbers, pad with -1 .
- X
- XDo not output a line consisting of -1 -1 .
- X
- XExample input file:
- X9
- X8
- X12
- X13
- X2
- X4
- X-1
- X
- XThe output should be:
- X9 8
- X13 12
- X-1 2
- X-1 4
- X
- XAnother example file:
- X9
- X11
- X13
- X2
- X4
- X7
- X-1
- X
- XThe output should be
- X9 2
- X11 4
- X13 -1
- X7 -1
- END_OF_FILE
- if test 864 -ne `wc -c <'prob4.txt'`; then
- echo shar: \"'prob4.txt'\" unpacked with wrong size!
- fi
- # end of 'prob4.txt'
- fi
- if test -f 'prob5.txt' -a "${1}" != "-c" ; then
- echo shar: Will not clobber existing file \"'prob5.txt'\"
- else
- echo shar: Extracting \"'prob5.txt'\" \(1051 characters\)
- sed "s/^X//" >'prob5.txt' <<'END_OF_FILE'
- XProblem 5: count the number of words in a text file.
- X
- XThe input file will consist of some number of lines.
- XThere will be only lowercase letters and blanks (and of course,
- Xnewlines) in the input file. (I.e., no tabs).
- XEach line will have zero or more non-blank strings separated
- Xby one or more blanks. Leading blanks are permitted in the input file.
- XA "word" is defined as a "string which does not contain a blank".
- XYour program should produce exactly as many lines as there are
- Xlines in the input file. Your output should be the integer number
- Xrepresenting the number of "words" on the corresponding input line.
- X
- XExample: if the input file consists of exactly six lines:
- Xnow is the time
- Xfor all
- X thirty days hath
- X september
- X
- X testing testing cqcqcq de k4xe
- X
- XThen your output would be
- X4
- X2
- X3
- X1
- X0
- X5
- X <this line is not part of your output>
- XPay particular attention to the fact that a blank line should
- Xproduce a zero-count in your output file. To emphasize:
- XYou should produce some output for each line of input, even if
- Xit is totally blank.
- END_OF_FILE
- if test 1051 -ne `wc -c <'prob5.txt'`; then
- echo shar: \"'prob5.txt'\" unpacked with wrong size!
- fi
- # end of 'prob5.txt'
- fi
- if test -f 'prob6.txt' -a "${1}" != "-c" ; then
- echo shar: Will not clobber existing file \"'prob6.txt'\"
- else
- echo shar: Extracting \"'prob6.txt'\" \(988 characters\)
- sed "s/^X//" >'prob6.txt' <<'END_OF_FILE'
- XProblem 6: Count the relationships.
- X
- XThe input file will contain an unknown number of lines each
- Xhaving four positive integers. The last line will be
- X -1 -1 -1 -1
- X
- XDo not output anything for the last line; it's there for use
- Xas a sentinel.
- X
- XThe numbers on each line are guaranteed to be distinct; that is,
- Xno number will appear more than once in the quartet of numbers.
- X
- XFor each line, count the number of times a smaller number appears
- Xto the left of a larger number, and also count the number of times
- Xa larger number appears to the left of a smaller number;
- Xfor example, if the four numbers are
- X 7 9 27 23
- Xthe "lessthan" count is 5, because 7<9, 7<27, 7<23, 9<27, 9<23,
- Xbut 27>23; the "greaterthan" count is 1, because 27>23.
- X
- XYour output should be: the original four numbers followed by
- Xthe lessthan-count and the greaterthan-count all on one line.
- X
- XEach input line should generate one output line.
- X
- XFor example, your output line for the above input line would be:
- X 7 9 27 23 5 1
- X
- END_OF_FILE
- if test 988 -ne `wc -c <'prob6.txt'`; then
- echo shar: \"'prob6.txt'\" unpacked with wrong size!
- fi
- # end of 'prob6.txt'
- fi
- if test -f 'sb.c' -a "${1}" != "-c" ; then
- echo shar: Will not clobber existing file \"'sb.c'\"
- else
- echo shar: Extracting \"'sb.c'\" \(1719 characters\)
- sed "s/^X//" >'sb.c' <<'END_OF_FILE'
- X#include <stdio.h>
- X#define newline '\n'
- X#define blank ' '
- X#define tab '\t'
- X#define indent {myputs(line);ilev++;goto lbl;}
- X#define undent {ilev--;myputs(line);goto lbl;}
- Xint ilev = 0;
- Xmain(argc,argv) char **argv;
- X{
- X char line[512], *a;
- X int i;
- X
- X while(gets(line)==line){
- X a=line;
- X while(*a){if(*a==newline)*a=0; a++;}
- X if(endsin(line,"then")==0){
- X indent }
- X if(endsin(line,"else")==0){
- X
- X ilev--; myputs(line); ilev++;goto lbl;
- X }
- X if(endsin(line,"fi")==0){
- X undent }
- X if(endsin(line,"done")==0){
- X undent }
- X if(endsin(line,"do")==0){
- X indent }
- X if(begins(line,"case")==0){
- X indent }
- X if(endsin(line,"esac")==0){
- X undent }
- X myputs(line);
- Xlbl: ;
- X }
- X}
- Xmyputs(p)char *p;
- X{
- X int i;
- X while(*p==blank ||*p==tab)p++;
- X if(ilev>0)for(i=1;i<=ilev;i++)printf(" ");
- X/* printf("%d",ilev);*/
- X puts(p);
- X}
- X
- Xendsin(a,b)
- Xchar *a, *b;
- X{
- X char *aa;
- X int i;
- X aa=a;
- X while(*aa==blank || *aa==tab)aa++;
- X if(strlen(a)<strlen(b))return -1;
- X a = a +strlen(a)-strlen(b);
- X i= kindex(a,b);
- X if(strlen(aa)==strlen(b))return i;
- X a--;
- X if(*a==tab||*a==';'||*a==blank)return i; else return -1;
- X/* printf("in endsin, a=%s b=%s returning %d\n",a,b,i);*/
- X/* fflush(stdout);*/
- X/* return i;*/
- X
- X}
- X
- X
- X
- X
- X
- Xbegins(a,b)
- Xchar *a, *b;
- X{
- X int i;
- X while(*a==blank || *a==tab)a++;
- X return kindex(a,b);
- X
- X}
- X
- X
- X
- X
- Xkindex(s,t)
- Xchar s[],t[];
- X{
- X int c,i,j,k;
- X c=s[0];
- X if(c==0){return -1;
- X/* i=puts("in kindex ... dummy, s[0] is zero");j=i;*/
- X/* puts(t);*/
- X/* if(i==j)exit(1);*/
- X }
- X c=t[0];
- X if(c==0){return -1;
- X/* i=puts("in kindex ... dummy, t[0] is zero");j=i;*/
- X/* puts(s);*/
- X/* if(j==i)exit(1);*/
- X }
- X for(i=0;s[i] !='\0'; i++){
- X for(j=i,k=0;t[k] !='\0' && s[j]==t[k];j++,k++)
- X ;
- X if(t[k]=='\0')return (i);
- X }
- X return(-1);
- X}
- END_OF_FILE
- if test 1719 -ne `wc -c <'sb.c'`; then
- echo shar: \"'sb.c'\" unpacked with wrong size!
- fi
- # end of 'sb.c'
- fi
- if test -f 'start' -a "${1}" != "-c" ; then
- echo shar: Will not clobber existing file \"'start'\"
- else
- echo shar: Extracting \"'start'\" \(1067 characters\)
- sed "s/^X//" >'start' <<'END_OF_FILE'
- X
- X#! /bin/sh
- X
- X#judges mailbox
- XMAIL=$MAIL
- X
- X#a public dir where score lives
- X#(the scoreboard should be local an only readable by judges,
- X# cause "score should be setuid judges)
- XLOCAL=/usr/contest
- X
- X#four hours:
- XLENGTH=14400
- X
- Xcd $HOME
- Xrm -f /tmp/prob*.txt
- X
- X
- Xrm -f t[0-9]*[0-9]*
- Xrm -f keep/*
- Xrm -f subdir/*
- X
- X#version:21
- Xecho "21">xxxx
- X/bin/cp /dev/null listofteams
- X
- Xwhile :
- Xdo
- Xread teamno
- Xcase $teamno in
- X "") echo null team number;exit;;
- X -1)break;
- Xesac
- Xecho team$teamno>>listofteams
- Xread cat
- Xread name
- X
- X
- X echo $teamno $cat $name >>xxxx
- X echo $teamno $cat $name
- X
- X
- Xdone
- Xecho "-1 -1 xx">>xxxx
- X#change the following line to y for a live start
- Xzork=y
- Xcase $zork in
- X y)
- X for i in 1 2 3 4 5 6 13 14 15 16 17 18
- X do
- X /bin/cp prob$i.txt /tmp
- X done ;;
- Xesac
- Xchmod og+r /tmp/*.txt
- X
- X/bin/cp scoreboard scoreboard.old
- Xseconds=`${LOCAL}/seconds`
- Xecho $seconds >> xxxx
- Xecho $seconds > starttime
- Xecho endtime = $endtime
- Xendtime=`expr $seconds '+' ${LENGTH}`
- Xecho endtime = $endtime
- Xecho $endtime > endtime
- X/bin/cp xxxx scoreboard
- Xchmod og-rwx scoreboard
- X
- X
- X${LOCAL}/score
- Xn mal
- Xn ${MAIL}
- END_OF_FILE
- if test 1067 -ne `wc -c <'start'`; then
- echo shar: \"'start'\" unpacked with wrong size!
- fi
- chmod +x 'start'
- # end of 'start'
- fi
- echo shar: End of archive 2 \(of 3\).
- cp /dev/null ark2isdone
- MISSING=""
- for I in 1 2 3 ; do
- if test ! -f ark${I}isdone ; then
- MISSING="${MISSING} ${I}"
- fi
- done
- if test "${MISSING}" = "" ; then
- echo You have unpacked all 3 archives.
- rm -f ark[1-9]isdone
- else
- echo You still need to unpack the following archives:
- echo " " ${MISSING}
- fi
- ## End of shell archive.
- exit 0
-
-